package com.lwt.codetop.linkedLists;
//143. 重排链表

import java.util.List;

/**
 * 思路：1. 获取到链表的中间节点，将后半部分进行翻转
 *      2. 交替拼接前后两部分链表（注意：原题无返回类型，为此要将两段在原有的基础上拼接的）
 */
public class ReorderList {
    public static void main(String[] args) {
        // 构建测试用例
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        // 1. 获取中间节点
        ListNode t = getMid(head);
        // 2. 翻转后半部分链表
        ListNode hou = reverse(t);


        // 3. 交替拼接两段链表
        merge(head, hou);

        // 4. 输出
        while (head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }

    }

    /**
     * 获取链表的中间节点
     * @param head
     * @return
     */
    private static ListNode getMid(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 翻转链表
     * @param head
     * @return
     */
    private static ListNode reverse(ListNode head) {
        ListNode a = head, b = a.next;
        while(b != null){
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        head.next = null;
        return a;
    }
    private static void merge(ListNode list1, ListNode list2) {
        while(list1 != null && list2 != null){
            ListNode n1 = list1.next, n2 = list2.next;
            list1.next = list2;
            list2.next = n1;
            list1 = n1;
            list2 = n2;
        }
    }
}
